// https://www.lintcode.com/problem/climbing-stairs/

public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int climbStairs(int n) {
        // write your code here
        if (n <= 2) {
            return n;
        }
        else {
            int ret = 0;
            int[] steps = new int[]{1, 2};
            for (int i = 2; i < n; ++i) {
                ret = steps[0] + steps[1];
                steps[0] = steps[1];
                steps[1] = ret;
            }
            return ret;
        }
    }
}